package search

// 二分查找
// 针对排好序的数据
// 时间复杂度 O(log(n))
//
// 局限性：
// 1.依赖顺序表结构，即数组（二分查找需要按照下标随机访问元素）
// 2.二分查找针对的是有序数据
// 3.数据量太小不太适合二分查找（但是当数据比较操作更耗时时，二分查找可以尽量减少比较次数）
// 4.数据量太大也不适合二分查找（二分查找依赖数组，而数组需要连续内存空间来支持随机访问）
//
// 4种常见的二分查找变形问题：
// - 查找第一个值等于给定值的元素
// - 查找最后一个值等于给定值的元素
// - 查找第一个大于等于给定值的元素
// - 查找最后一个小于等于给定值的元素
//
// 二分查找更适合用在"近似"查找的问题，等于查找更多的使用散列表、二叉树或者堆来实现.

type BinarySearch func(arr []int, param int) (index int, find bool)

// 查找最后一个小于等于给定值的元素
func FindLastSmallOrEqualByBinarySearch(arr []int, param int) (index int, find bool) {
	low, high := 0, len(arr)-1

	for low <= high {
		midIndex := (high-low)>>1 + low
		midVal := arr[midIndex]

		if midVal <= param {
			if midIndex == len(arr)-1 || arr[midIndex+1] > param {
				return midIndex, true
			} else {
				low = midIndex + 1
			}
		} else {
			high = midIndex - 1
		}
	}

	return -1, false
}

// 查找第一个大于等于给定值的元素
func FindFirstBigOrEqualByBinarySearch(arr []int, param int) (index int, find bool) {
	low, high := 0, len(arr)-1

	for low <= high {
		midIndex := (high-low)>>1 + low
		midVal := arr[midIndex]

		if midVal >= param {
			if midIndex == 0 || arr[midIndex-1] < param {
				return midIndex, true
			} else {
				high = midIndex - 1
			}
		} else {
			low = midIndex + 1
		}
	}
	return -1, false
}

// 查找最后一个值等于给定值的元素
func FindLastEqualByBinarySearch(arr []int, param int) (index int, find bool) {
	low, high := 0, len(arr)-1

	for low <= high {
		midIndex := (high-low)>>1 + low
		midVal := arr[midIndex]

		if midVal == param {
			if midIndex == len(arr)-1 || arr[midIndex+1] != param {
				return midIndex, true
			} else {
				low = midIndex + 1
			}
		} else if midVal > param {
			high = midIndex - 1
		} else {
			low = midIndex + 1
		}
	}
	return -1, false
}

// 查找第一个值等于给定值的元素
func FindFirstEqualByBinarySearch(arr []int, param int) (index int, find bool) {
	low, high := 0, len(arr)-1

	for low <= high {
		midIndex := (high-low)>>1 + low
		midVal := arr[midIndex]

		if midVal == param {
			if midIndex == 0 || arr[midIndex-1] != param {
				return midIndex, true
			} else {
				high = midIndex - 1
			}
		} else if midVal > param {
			high = midIndex - 1
		} else {
			low = midIndex + 1
		}
	}
	return -1, false
}

// 简单二分查找
// 需要元素有序（从小到大）且不重复.
func SimpleBinarySearch(arr []int, param int) (index int, find bool) {
	low, high := 0, len(arr)-1

	for low <= high {
		midIndex := (high-low)>>1 + low
		midVal := arr[midIndex]

		if midVal == param {
			return midIndex, true
		} else if midVal > param {
			high = midIndex - 1
		} else {
			low = midIndex + 1
		}
	}
	return -1, false
}

// 简单二分查找的递归实现
// 需要元素有序（从小到大）且不重复.
func SimpleBinarySearchRecursively(arr []int, param int) (index int, find bool) {
	n := len(arr)
	return simpleBinarySearchRecursively(arr, 0, n-1, param)
}

func simpleBinarySearchRecursively(arr []int, low int, high int, param int) (index int, find bool) {
	if low > high {
		return -1, false
	}

	midIndex := (high-low)>>1 + low
	midVal := arr[midIndex]

	if midVal == param {
		return midIndex, true
	} else if midVal > param {
		return simpleBinarySearchRecursively(arr, low, midIndex-1, param)
	} else {
		return simpleBinarySearchRecursively(arr, midIndex+1, high, param)
	}
}
